package com.gaogzhen.algorithm.search;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class FabonacciSearch {

    public static boolean notNull(int[] a) {
        return a != null && a.length > 0;
    }

    public static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }

    public static int[] fabonacciArray(int len) {
        List<Integer> f = new LinkedList<>();
        int f1 = 1, f2 = 1;
        if (len == 1) {
            f.add(f1);
        } else {
            f.add(f1);
            f.add(f2);
            int t;
            while (len > (t = f1 + f2)) {
                f1 = f2;
                f2 = t;
                f.add(t);
            }
            f.add(t);
        }
        return f.stream().mapToInt(Integer::valueOf).toArray();

    }

    public static int search(int[] a, int key) {
        return search(a, 0, a.length, key);
    }

    public static  int search(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        int[] fab = fabonacciArray(toIndex);
        // 长度补齐
        int adaptLen = fab[fab.length - 1];
        int[] temp = Arrays.copyOf(a, adaptLen);
        for (int i = toIndex; i < adaptLen; i++) {
            temp[i] = temp[high];
        }
        int k = fab.length - 1;
        while (low <= high) {
            int mid = low + fab[k - 1] - 1;
            if (temp[mid] < key) {
                low = mid + 1;
                k -= 2;
            } else if (temp[mid] > key) {
                high = mid - 1;
                k--;
            } else {
                return mid <= high ? mid: high;
            }
        }
        return -1;
    }
}
